package tulingxueyuan117;

import java.util.Arrays;

/**
 * Author: Zhang Dongwei
 * Date: 2022/11/26 16:29
 */
public class p56_字符串匹配之KMP_28 {
    public static void main(String[] args) {
        String haystack = "abeababeabf", needle = "abeabf";
        System.out.println(strStr(haystack, needle));
    }

    public static int strStr(String haystack, String needle) {
        if (needle.isEmpty()) return 0;
        int n = haystack.length(), m = needle.length();
//        原串和匹配串前面都加个空格，使其下标从1开始
        haystack = " " + haystack;
        needle = " " + needle;

        char[] s = haystack.toCharArray();
        char[] p = needle.toCharArray();

//        构建next数组，数组长度为匹配串长度
        int[] next = new int[m+1];
//        构造过程i=2,j=0开始,i小于等于匹配串长度
        for (int i = 2, j = 0; i <= m; i++){
//            匹配不成功，j=next[j]
            while (j > 0 && p[i] != p[j+1]) j = next[j];
//            匹配成功，先让j++
            if (p[i] == p[j+1]) j++;
//            更新next[i]，结束本次循环，i++
            next[i] = j;
        }

//        System.out.println(Arrays.toString(next));
//        匹配过程，i=1, j=0开始，i小于等于原串长度
        for (int i = 1, j=0; i <= n; i++){
//            匹配不成功，j=next(j)
            while (j > 0 && s[i] != p[j+1]) j = next[j];
//            匹配成功，先让j++,结束本次循环后 i++
            if (s[i] == p[j+1]) j++;

            if (j == m) return i - m;
        }
        return -1;
    }
}
